import math
import random
from collections import defaultdict

def euclidean_distance(point1, point2):
   
    if len(point1) != len(point2):
        raise ValueError("点的维度不匹配")
    
    squared_distance = 0
    for i in range(len(point1)):
        squared_distance += (point1[i] - point2[i]) ** 2
    
    return math.sqrt(squared_distance)

def assign_cluster(x, centroids):
  
    min_distance = float('inf')
    closest_centroid = 0
    
    for i, centroid in enumerate(centroids):
        distance = euclidean_distance(x, centroid)
        if distance < min_distance:
            min_distance = distance
            closest_centroid = i
    
    return closest_centroid

def initialize_centroids(data, k):
   
    # 从数据中随机选择k个不同的点作为初始中心
    return random.sample(data, k)

def update_centroids(clusters):
   
    new_centroids = []
    
    for cluster_points in clusters.values():
        if not cluster_points:
            # 如果簇为空，随机选择一个点作为中心
            new_centroids.append(random.choice([point for cluster in clusters.values() for point in cluster]))
            continue
            
        # 计算每个维度的均值
        n_dimensions = len(cluster_points[0])
        centroid = []
        
        for dim in range(n_dimensions):
            dimension_sum = sum(point[dim] for point in cluster_points)
            dimension_mean = dimension_sum / len(cluster_points)
            centroid.append(dimension_mean)
        
        new_centroids.append(centroid)
    
    return new_centroids

def has_converged(old_centroids, new_centroids, epsilon):
  
    for old_centroid, new_centroid in zip(old_centroids, new_centroids):
        distance = euclidean_distance(old_centroid, new_centroid)
        if distance > epsilon:
            return False
    return True

def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
   
    # 参数检查
    if len(data) < k:
        raise ValueError("数据点数量不能小于聚类数量k")
    
    if k <= 0:
        raise ValueError("聚类数量k必须大于0")
    
    # 初始化聚类中心
    centroids = initialize_centroids(data, k)
    
    for iteration in range(max_iterations):
        # 分配数据点到最近的簇
        clusters = defaultdict(list)
        
        for point in data:
            cluster_idx = assign_cluster(point, centroids)
            clusters[cluster_idx].append(point)
        
        # 检查是否有空簇
        empty_clusters = [idx for idx in range(k) if idx not in clusters]
        if empty_clusters:
            # 处理空簇：从最大的簇中随机选择一个点作为新中心
            largest_cluster = max(clusters.items(), key=lambda x: len(x[1]))
            for empty_idx in empty_clusters:
                random_point = random.choice(largest_cluster[1])
                clusters[empty_idx] = [random_point]
        
        # 更新聚类中心
        new_centroids = update_centroids(clusters)
        
        # 检查收敛
        if has_converged(centroids, new_centroids, epsilon):
            print(f"算法在第 {iteration + 1} 次迭代后收敛")
            break
        
        centroids = new_centroids
    
    else:
        print(f"达到最大迭代次数 {max_iterations}")
    
    return dict(clusters), centroids

def calculate_wcss(clusters, centroids):
  
    wcss = 0
    for cluster_idx, points in clusters.items():
        centroid = centroids[cluster_idx]
        for point in points:
            wcss += euclidean_distance(point, centroid) ** 2
    return wcss

# 测试代码
if __name__ == "__main__":
    # 创建测试数据
    random.seed(42)  # 设置随机种子以便复现结果
    
    # 生成三组简单的二维数据
    test_data = []
    # 第一组数据
    for _ in range(30):
        test_data.append([random.gauss(2, 0.5), random.gauss(2, 0.5)])
    # 第二组数据
    for _ in range(30):
        test_data.append([random.gauss(8, 0.5), random.gauss(8, 0.5)])
    # 第三组数据
    for _ in range(30):
        test_data.append([random.gauss(5, 0.5), random.gauss(2, 0.5)])
    
    print("数据集大小:", len(test_data))
    print("前5个数据点:", test_data[:5])
    
    # 运行K均值聚类
    k = 3
    clusters, centroids = Kmeans(test_data, k, epsilon=0.001, max_iterations=100)
    
    # 输出结果
    print(f"\n聚类结果 (k={k}):")
    for cluster_idx, points in clusters.items():
        print(f"簇 {cluster_idx}: {len(points)} 个点")
        print(f"  中心点: {centroids[cluster_idx]}")
    
    # 计算簇内平方和
    wcss = calculate_wcss(clusters, centroids)
    print(f"\n簇内平方和 (WCSS): {wcss:.4f}")
    
    # 测试 assign_cluster 函数
    print(f"\n测试 assign_cluster 函数:")
    test_point = [3, 3]
    assigned_cluster = assign_cluster(test_point, centroids)
    print(f"点 {test_point} 被分配到簇 {assigned_cluster}")